package com.jlh.viewer.algorithm;

/**
 * Created by jlh
 * On 2017/3/17 0017.
 */
public class TreeBin<T extends Comparable> {
    private static final boolean BLACK=true;
    private static final boolean RED=false;
    private TreeNode<T> root;
    private Integer size;

    public TreeBin() {
        root=new TreeNode<T>();
        root.color=BLACK;
        root.left=null;
        root.right=null;
        root.parent=null;
        size=0;
    }

    public boolean push (T v){
        TreeNode<T> node = findNode(v);
        node.value=v;
        size++;
        adjust(node);
        return true;
    }


    private void adjust(TreeNode<T> t){
        TreeNode<T> parent,gparent;
        while ((parent=t.parent)!=null&&parent.color==RED){
            gparent=parent.parent;
            //父节点是祖父节点的左节点
            if (parent==gparent.left){
                TreeNode<T> uncle= gparent.right;
                //1. 叔叔节点是黑色的 节点是父节点的左子树
                if((uncle==null||uncle.color==BLACK)&&(t==parent.left)){
                    parent.color=BLACK;
                    gparent.color=RED;
                    rightRotate(gparent);
                }
                // 叔叔是黑色的 节点是父节点的右子树
                else if ((uncle==null||uncle.color==BLACK)&&t==parent.right){
                    t.color=BLACK;
                    gparent.color=RED;
                    leftRotate(parent);
                    rightRotate(gparent);
                }

            }else {//父节点是祖父节点的右节点
                TreeNode<T> uncle= gparent.left;
                // 叔叔是黑色的 节点是父节点的右子树
                if((uncle==null||uncle.color==BLACK)&&(t==parent.right)){
                    parent.color=BLACK;
                    gparent.color=RED;
                    leftRotate(gparent);
                }
                // 叔叔是黑色的 节点是父节点的左子树
                else if ((uncle==null||uncle.color==BLACK)&&t==parent.left){
                    t.color=BLACK;
                    gparent.color=RED;
                    rightRotate(parent);
                    leftRotate(gparent);
                }

            }
        }
        root.color=BLACK;
    }

    private void leftRotate(TreeNode<T> x){
        // 设置x的右孩子为y
        TreeNode<T> y = x.right;

        // 将 “y的左孩子” 设为 “x的右孩子”；
        // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
        x.right = y.left;
        if (y.left != null)
            y.left.parent = x;

        // 将 “x的父亲” 设为 “y的父亲”
        y.parent = x.parent;

        if (x.parent == null) {
            this.root = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
        } else {
            if (x.parent.left == x)
                x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
            else
                x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
        }

        // 将 “x” 设为 “y的左孩子”
        y.left = x;
        // 将 “x的父节点” 设为 “y”
        x.parent = y;
    }

    private void rightRotate(TreeNode<T> y){
        TreeNode<T> x= y.left;
        y.left=x.right;
        if (x.right!=null){
            x.right.parent=y;
        }
        x.parent=y.parent;
        if (y.parent==null){
            root=x;
        }else {
            if (y.parent.left==y)
                y.parent.left=x;
            else
                y.parent.right=x;
        }
        x.right=y;
        y.parent=x;
    }

    private TreeNode<T> findNode(T v){
        if (size.equals(0))
            return root;
        TreeNode<T> p = root;
        while (true){
            if (p.value.compareTo(v)>0&&p.left!=null)
                p=p.left;
            else if (p.value.compareTo(v)>0&&p.left==null){
                p.left=createChild(p);
                return p.left;
            }
            else if (p.value.compareTo(v)<=0&&p.right!=null)
                p=p.right;
            else if (p.value.compareTo(v)<=0&&p.right==null){
                p.right=createChild(p);
                return p.right;
            }

        }
    }

    private TreeNode<T> createChild(TreeNode<T> p){
        TreeNode<T> child= new TreeNode<T>();
        child.left=null;
        child.right=null;
        child.parent=p;
        return child;
    }


    public static void main(String[] args) {
        TreeBin<Integer> treeBin = new TreeBin<>();
        treeBin.push(2);
        treeBin.push(1);
        treeBin.push(3);
        treeBin.push(4);
        System.out.println(treeBin);
    }
    private static class TreeNode <K extends Comparable>{
        /**
         * 节点的颜色，false代表红色，true代表黑色
         */
        private Boolean color =RED ;
        /**
         * 节点值
         */
        private K value;
        /**
         * 左节点
         */
        private TreeNode<K> left;
        /**
         * 右节点
         */
        private TreeNode<K> right;
        /**
         * 父节点
         */
        private TreeNode<K> parent;

    }

    @Override
    public String toString() {
        return "TreeBin{" +
                "root=" + root +
                ", size=" + size +
                '}';
    }
}
